In modern communication networks, a large number of network devices send and receive network communication messages for a wide range of uses. In many applications, the receiver of a network communication message needs to be able to verify the authenticity of a communication message. As used herein, the term “verification” refers to a process for determining if a message is authentic and determining if the integrity of the message has been compromised. An authentic message means that the party purporting to be the sender of the message is in fact the party that sent the message. Message integrity refers to a determination that the contents of the message received by a recipient have not been altered after having been sent from the purported sender. Attackers attempt to forge communication messages that appear to be from a trusted sender, but that are not actually from the sender, or the attackers eavesdrop on legitimate messages from the sender and attempt to spoof the receiver with copies of the legitimate messages. The message verification process prevents the attacker from convincing the recipient that the message is from a trusted party or that the contents of a copied message can be trusted.
There are several existing techniques that enable a message recipient to verify network communication messages. Most of the existing techniques, however, are directed to unicast or one-to-one communications where a single sender communicates with a single recipient. In some network configurations, a network device sends multicast or broadcast messages to a plurality of recipient network devices. The term “broadcast” refers to sending a message to each of a plurality of other network devices that are associated as members of a single group, and the term “multicast” refers to sending a message to more than one, but less than all, of the associated network devices. One example of an associated group of network devices is a sensor network including a plurality of networked sensor devices that communicate with each other. Other examples include supervisory control and data acquisition (SCADA) systems and more broadly include groups of network devices that send and receive network messages with one another as part of embedded computer networks.
While existing message verification techniques can be applied to multicast and broadcast network devices, the existing techniques have limitations in broadcast and multicast networks. The network devices in many sensor networks have limited computational power and limited data storage space that render many traditional message verification techniques prohibitively expensive from a computational standpoint. For example, the traditional signature and verification process in public key cryptography can be too computationally expensive for such devices, especially when the devices must send time-critical messages. Existing techniques to improve the efficiency of public key cryptography, such as signature amortization, require that the verification process be spread over multiple communication messages. This requirement can delay the verification of the communication messages and present difficulties if one or more communication messages are lost or corrupted. Another public-private key technique uses one-time public/private signatures (OTS) to sign messages and verify. While the OTS techniques are more computationally efficient than using traditional public and private key techniques, the OTS system must distribute to each of the message recipients a large number of public keys that are used only once. In a broadcast or multicast network, the amount of data required to distribute the public keys to all of the recipients can overwhelm the network communication devices. Still other verification techniques use online/offline signature generation where a portion of the signature can be pre-computed prior to signing and sending a message. However, the online/offline signature systems either require a large amount of storage space to hold pre-computed data or require computationally expensive operations during message verification. Other forms of message verification including symmetric-key systems that are either less secure because all of the devices share a single secret key, or do not scale when each pair of devices needs to manage a separate set of secret keys.
As described above, existing techniques for message verification have various drawbacks, especially in broadcast and multicast systems with limited computing power and data storage. Given the above deficiencies with existing message verification techniques, improvements to message verification in data networks would be beneficial.